package code.sort;

import java.net.InetAddress;

public class MergeSort {
    //使用递归实现归并排序
    public void mergeSort(int[] arry){
        process(arry,0,arry.length -1);
    }

    public void process(int [] arry,int left,int right){
        if(left == right){
            return ;
        }
        int mid  = (left + right)/2;
        process(arry,left,mid-1);
        process(arry,mid +1,right);
        merge(arry,left,mid,right);
    }
    public void merge(int [] arry,int left,int mid,int right){
        int[] help = new int [right -left +1];
        int p1 = left;
        int p2 = mid +1;
        int i = 0;
        while (p1<=mid && p2<=right){
            help[i++] =arry[p1] < arry[p2]? arry[p1++]:arry[p2++];
        }
        while (p1 <= mid){
            help[i++] = arry[p1++];
        }
        while (p2 <= right){
            help[i++] = arry[p2++];
        }
        for (int j = 0; j <help.length; j++) {
            arry[left+i]= help[i];
        }
    }


    //非递归方法实现,使用步长的方式
    public  void merge(int[] arry){
        if(arry == null ||arry.length ==0 || arry.length ==1){
            return;
        }
        int length = arry.length;
        int mergeSize = 1;
        while (mergeSize < length){
            int L = 0;
            while (L < length){
                int M = L + mergeSize;
                if(M >=length){
                    break;
                }
                int R = Math.min(M+mergeSize,length);
                merge(arry,length,M,R);
                L = R + 1;
            }
            if(mergeSize >length/2){
                break;
            }
            mergeSize <<= 1;
        }
    }


    public void merge2(int [] arry) {
        int N = arry.length;
        int mergeSize = 1;
        while (mergeSize<N){
            int L = 0;
            while (L < N){
                int M = L + mergeSize;
                if(M >= N){
                    break;
                }
                int R = Math.min(M +mergeSize,N);
                merge(arry,L,M,R);
                L = R+1;
            }

            mergeSize >>= 1;
        }
    }
}
